using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DependencyAnalysis.Algorithms.SubstringDetection
{
    public class GeneralizedSuffixTree
    {
        public const char Delimiter = '\ufffe';

        private readonly char[][] _texts;

        private readonly int[] _offsets;
        private readonly SuffixTree _suffixTree;

        public GeneralizedSuffixTree(char[][] texts)
        {
            var terminators = GetDefaultTerminators(texts.Length);
            _texts = texts;
            _offsets = new int[texts.Length];
            int currentOffset = 0;
            var stringBuilder = new StringBuilder();
            for (int i = 0; i < texts.Length; i++)
            {
                stringBuilder.Append(texts[i]);
                stringBuilder.Append(terminators[i]);
                _offsets[i] = currentOffset;
                currentOffset += texts[i].Length + 1;
            }
            char[] generalized = stringBuilder.ToString().ToCharArray();
            _suffixTree = new SuffixTree(generalized);
            FixSpanSuffixes(_suffixTree.RootNode);
        }

        private void FixSpanSuffixes(Node node)
        {
            foreach (Edge edge in node.GetEdges())
            {
                for (int i = 0; i < _texts.Length; i++)
                {
                    int length = GetGeneralizedSubstringLength(i);
                    if ((edge.BeginIndex <= length) &&
                        (edge.EndIndex > length))
                    {
                        edge.EndIndex = length;
                    }
                }
                FixSpanSuffixes(edge.EndNode);
            }
        }

        private int GetGeneralizedSubstringLength(int n)
        {
            return _offsets[n] + _texts[n].Length;
        }

        public CommonSubstring FindLongestCommonSubstring()
        {
            int[] beginIndexes = new int[_texts.Length];
            int[] endIndexes = new int[_texts.Length];
            InitBeginEndIndexes(beginIndexes, endIndexes);

            var statuses = new Dictionary<Node, CommonSubstringStatus>();
            GetLcsNodeStatus(_suffixTree.RootNode, 0, statuses);

            CommonSubstring commonSubstring = FindLongestCommonSubstring(beginIndexes, endIndexes, statuses);
            statuses.Clear();

            return commonSubstring;
        }

        private void InitBeginEndIndexes(int[] beginIndexes, int[] endIndexes)
        {
            beginIndexes[0] = 0;
            endIndexes[0] = _texts[0].Length;

            for (int i = 1; i < _texts.Length; i++)
            {
                beginIndexes[i] = endIndexes[i - 1] + 1;
                endIndexes[i] = beginIndexes[i] + _texts[i].Length;
            }
        }

        public static char[] GetDefaultTerminators(int length)
        {
            char[] terminators = new char[length];
            for (int i = 0; i < length; i++)
                terminators[i] = (char)(1000 + i % 50000);
            return terminators;
        }

        public int[] IncIndexes(int[] indexes)
        {
            for (int i = 0; i < _texts.Length; i++)
                indexes[i]++;
            return indexes;
        }

        private CommonSubstring FindLongestCommonSubstring(int[] beginIndexes, int[] endIndexes, IDictionary<Node, CommonSubstringStatus> statuses)
        {
            int max = 0;
            int[] foundBeginIndexes = null;

            foreach (CommonSubstringStatus status in statuses.Values)
            {
                if ((status.Height > 0) && (status.IsInAllStrings()) && (max <= status.Height))
                {
                    Node node = status.Node;
                    int[] workingBeginIndexes = InitFoundBeginIndexes();

                    UpdateFoundBeginIndexes(new UpdateFoundBeginIndexesParams(beginIndexes, endIndexes, node, status.Height, statuses, workingBeginIndexes));

                    if (VerifyFoundBeginIndexes(workingBeginIndexes))
                    {
                        foundBeginIndexes = workingBeginIndexes;
                        max = status.Height;
                    }
                }
            }

            if (foundBeginIndexes == null)
                return null;
            for (int i = 0; i < foundBeginIndexes.Length; i++)
            {
                foundBeginIndexes[i] -= _offsets[i];
            }
            return new CommonSubstring { BeginIndices = foundBeginIndexes, Length = max };
        }

        private int[] InitFoundBeginIndexes()
        {
            int[] beginIndexes = new int[_texts.Length];
            for (int i = 0; i < _texts.Length; i++)
                beginIndexes[i] = int.MaxValue;
            return beginIndexes;
        }

        internal class UpdateFoundBeginIndexesParams
        {
            private readonly int[] _beginIndexes;
            private readonly int[] _endIndexes;
            private readonly Node _node;
            private readonly int _height;
            private readonly IDictionary<Node, CommonSubstringStatus> _statuses;
            private readonly int[] _foundBeginIndexes;

            public UpdateFoundBeginIndexesParams(int[] beginIndexes,
                int[] endIndexes,
                Node node,
                int height,
                IDictionary<Node,
                CommonSubstringStatus> statuses,
                int[] foundBeginIndexes)
            {
                _beginIndexes = beginIndexes;
                _endIndexes = endIndexes;
                _node = node;
                _height = height;
                _statuses = statuses;
                _foundBeginIndexes = foundBeginIndexes;
            }

            public int[] BeginIndexes
            {
                get { return _beginIndexes; }
            }

            public int[] EndIndexes
            {
                get { return _endIndexes; }
            }

            public Node Node
            {
                get { return _node; }
            }

            public int Height
            {
                get { return _height; }
            }

            public IDictionary<Node, CommonSubstringStatus> Statuses
            {
                get { return _statuses; }
            }

            public int[] FoundBeginIndexes
            {
                get { return _foundBeginIndexes; }
            }
        }

        private void UpdateFoundBeginIndexes(UpdateFoundBeginIndexesParams updateFoundBeginIndexesParams)
        {
            foreach (Edge edge in updateFoundBeginIndexesParams.Node.GetEdges())
            {
                CommonSubstringStatus nodeStatus = updateFoundBeginIndexesParams.Statuses.ContainsKey(edge.EndNode) ? updateFoundBeginIndexesParams.Statuses[edge.EndNode] : null;
                if ((nodeStatus != null) && nodeStatus.IsInAllStrings())
                {
                    UpdateFoundBeginIndexes(new UpdateFoundBeginIndexesParams(updateFoundBeginIndexesParams.BeginIndexes, updateFoundBeginIndexesParams.EndIndexes, edge.EndNode, updateFoundBeginIndexesParams.Height + GetEdgeHeight(edge), updateFoundBeginIndexesParams.Statuses, updateFoundBeginIndexesParams.FoundBeginIndexes));
                }
                else
                {
                    int stringNumber = GetEdgeStringNumber(edge);
                    int beginIndex = edge.BeginIndex - updateFoundBeginIndexesParams.Height;

                    if ((beginIndex < updateFoundBeginIndexesParams.EndIndexes[stringNumber]) &&
                        (beginIndex >= updateFoundBeginIndexesParams.BeginIndexes[stringNumber]) &&
                        (updateFoundBeginIndexesParams.FoundBeginIndexes[stringNumber] > beginIndex))
                    {

                        updateFoundBeginIndexesParams.FoundBeginIndexes[stringNumber] = beginIndex;
                    }
                }
            }
        }

        private bool VerifyFoundBeginIndexes(int[] beginIndexes)
        {
            for (int i = 0; i < _texts.Length; i++)
                if (beginIndexes[i] < 0)
                    return false;
            return true;
        }

        private int GetEdgeStringNumber(Edge edge)
        {
            for (int i = 0; i < _texts.Length; i++)
            {
                if (edge.EndIndex <= GetGeneralizedSubstringLength(i))
                    return i;
            }
            return -1;
        }

        private int GetEdgeHeight(Edge edge)
        {
            return edge.EndIndex - edge.BeginIndex;
        }

        private int GetEdgeHeightForNodeStatus(Edge edge)
        {
            int result = GetEdgeHeight(edge);

            int stringNumber = GetEdgeStringNumber(edge);
            if (edge.EndIndex != GetGeneralizedSubstringLength(stringNumber))
                result += 1;
            return result;
        }

        public IList<CommonSubstring> FindCommonSubstrings(int minimalLength)
        {
            var statuses = new Dictionary<Node, CommonSubstringStatus>();
            GetLcsNodeStatus(_suffixTree.RootNode, 0, statuses);
            var duplicates = (from x in statuses.Values
                              where x.IsInAtLeastTwoStrings() && x.Height >= minimalLength
                              select x).ToList();

            var substrings = RemoveInclusiveSubstrings(duplicates);
            foreach (var substring in substrings)
            {
                for (int i = 0; i < substring.TextIndices.Length; i++)
                {
                    substring.BeginIndices[i] -= _offsets[substring.TextIndices[i]];
                }
            }
            return substrings;
        }

        private IList<CommonSubstring> RemoveInclusiveSubstrings(IEnumerable<CommonSubstringStatus> duplicates)
        {
            var commonSubstrings = new List<CommonSubstring>();
            var longestSubstrings = new Dictionary<string, CommonSubstring>();
            foreach (var status in duplicates)
            {
                var edges = status.Node.GetEdges();
                var textIndices = (from x in edges select GetEdgeStringNumber(x)).ToArray();
                var stringBuilder = new StringBuilder();
                foreach (var textIndex in textIndices)
                {
                    stringBuilder.Append(textIndex);
                    stringBuilder.Append(',');
                }
                var key = stringBuilder.ToString();
                CommonSubstring substring;
                if (longestSubstrings.ContainsKey(key))
                {
                    substring = longestSubstrings[key];
                    if (substring.Length >= status.Height) continue;
                }
                else
                {
                    substring = new CommonSubstring { TextIndices = textIndices };
                    longestSubstrings[key] = substring;
                    commonSubstrings.Add(substring);
                }
                substring.Length = status.Height;
                substring.BeginIndices = (from x in edges select x.BeginIndex - status.Height).ToArray();

            }
            return commonSubstrings;
        }

        private CommonSubstringStatus GetLcsNodeStatus(Node node, int height, IDictionary<Node, CommonSubstringStatus> statuses)
        {
            var nodeStatus = new CommonSubstringStatus(node, height, _texts.Length);
            if (node.GetEdges().Length == 0)
            {
                return nodeStatus;
            }

            foreach (Edge edge in node.GetEdges())
            {
                CommonSubstringStatus status = GetLcsNodeStatus(edge.EndNode,
                                                        height + GetEdgeHeightForNodeStatus(edge), statuses);

                status.AddString(GetEdgeStringNumber(edge));
                nodeStatus.MergeStatus(status);
            }
            statuses[node] = nodeStatus;
            return nodeStatus;
        }

        /**
     * Suffix Tree Node Status for Longest Common Substring (LCS)
     */
    }
}